package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.HashSet;
import java.util.Set;

/**
 * 哈希<br>
 * 并查集、数组、哈希表<br>
 * 中等
 *
 * <H1>128. 最长连续序列</H1>
 *
 * <p>给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。</p>
 *
 * <p>请你设计并实现时间复杂度为 O(n) 的算法解决此问题。</p>
 */
public class A03LongestConsecutive {
    public static void main(String[] args) {
        A03LongestConsecutive longestConsecutive = new A03LongestConsecutive();

        int[] nums = new int[]{100,4,200,1,3,2};
        System.out.println("基础数据");
        TimeCostUtil.timeCost("哈希表", () -> longestConsecutive.solution1(nums));

        int[] nums2 = DataGeneratorUtil.generateRandomIntArray(1000000, 1, 1000000);
        System.out.println("大数据量");
        TimeCostUtil.timeCost("哈希表", () -> longestConsecutive.solution1(nums2));
    }

    /**
     * 哈希表
     * 判断一次这个数是不是连续序列的开头那个数
     * @param nums
     * @return
     */
    public int solution1(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        int longestStreak = 0;
        for (int num : numSet) {
            // 如果不是 num-1 的数字，则开始计算以 num 为开头的连续序列的长度
            // 因为 num -1 不存在，代表这个数一定不是开头的数
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}
